1. Field of the Invention
The present invention relates generally to the field of computer aided design/computer aided engineering (CAD/CAE), more particularly to the field of data array reordering in a CAD/CAE environment.
2. Description of Background Art
Computer aided design (CAD) and computer aided engineering (CAE) systems frequently increase computational speed by invoking a table (array) lookup technique. The table lookup technique is generally used to compute the results of a function having the following characteristics: (a) the function is repeated a large number of times; (b) for each computation the aggregate of the input to the function (domain) is a few bits, e.g., 4-16 bits; and (c) the output (range) can be represented by a few bytes, e.g., 1-8 bytes, for example. To implement the function, all possible results of the function (or a meaningful subset thereof) are calculated in advance and stored as a table (array) in a memory module of a computer. A methodology utilizing the table, as described below, is generated and stored in a computer readable format, e.g., as a computer program stored in a memory module of a computer, as firmware, or hardwired in computer hardware. For ease of discussion, the following description will presume the methodology is stored as a computer program. However, it will be apparent to persons skilled in the art that alternate techniques can be used to implement the computer based methodology of the present invention. The computer program catenates all of the bits that comprise the input to the function in a prescribed order, e.g., bits represented by w, x, y, z. These bits are treated as an integer in the range of zero to 2.sup.N -1, where N is equal to the number of input bits. This integer is used as an index (address) into the table (array) of pre-computed results. The results of the function are determined using a single memory reference to the table plus the time required to assemble the input bits. The time required to generate the results of the function using the table-lookup technique is typically significantly less than having the computer invoke the logic necessary to perform the function.
In complex CAD/CAE environments the success of the table-lookup technique frequently depends upon knowing the order of the address bits at the time the lookup-table is generated. In many computer-based disciplines the optimal order of the address bits is known when the table is generated because the address formation and the table contents are under the control of the programmer. However, in complex CAD/CAE environments, varying the sequence of the input bits can significantly alter the computational time of a CAD/CAE computer simulation, for example. Frequently, the optimal ordering of inputs is not determined until after the lookup-table and the simulation software have been generated. In this situation, it is not economically feasible to re-generate all of the, possibly thousands, of lookup-tables used in the computer program to match the new arrangement of input bits. Further complicating the problem is that the number of input bits for each lookup-table can vary significantly. What is needed is a system and method for rearranging the table entries after the table has been generated and after the computer program has been generated.
As indicated above, the rearrangement of input bits does not require the recalculation of a new lookup-table. Instead, rearranging the input bits requires merely the rearranging of the lookup-table entries. For example, an eight entry table can have an index having three address bits (x,y,z) that are catenated in order with "x" as the most significant bit. If the contents of the table can be identified as {A,B,C,D,E,F,G,H} in addresses 0-7 respectively, then x=0, y=0, z=0, yields "A", and x=1, y=1, z=1, yields "H". If it is determined that a CAD/CAE simulation will be more efficient if the three address bits are arranged as (y,x,z) when forming the address, the table entries must be rearranged into the order {A,B,E,F,C,D,G,H} in addresses 0-7 respectively.
FIG. 1 is an illustration of a table (array) having a four bit index. Each bit in the four bit index can be represented as a variable, e.g., w, x, y, and z respectively with "w" as the most significant bit. The table entries are represented as {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P} in addresses 0-15 respectively. For example when the index (w,x,y,z) is equal to (0000), the associated table entry is "A". Similarly when the index is (1111), the associated table entry is "P". As noted above, there are circumstances when it is more efficient to modify the bit sequence. For example, in some circumstances, it may be advantageous to modify the bit sequence from (w,x,y,z) to (z,w,x,y). As described above, if the index sequence is modified the table entries must be rearranged to match the new sequence.
One conventional technique for rearranging the table entries requires the swapping of two bits at a time and processing (rearranging) the table entries for each swap. FIGS. 2(a)-(c) are illustrations of an example of a table that is rearranged using a conventional two-bit swapping technique. In this example, the original table, (old table) is the table described above with reference to FIG. 1 having the index represented as (w,x,y,z). The modified index sequence is (z,w,x,y). FIG. 2(a) is an illustration of a first intermediate table representing the table after swapping the "z" bit and the "w" bit and re-processing the table to match the modified index. The table index illustrated in FIG. 2(a) is (z,x,y,w) and the table entries are {A,I,C,K,E,M,G,O,B,J,D,L,F,N,H,P} in addresses 0-15 respectively. Each table entry is copied and, if necessary, a new table entry is substituted for an old table entry. However, since only two index bits can be swapped at one time, the current index, i.e., (z,x,y,w), does not match the index of the new table and another bit swap is required.
FIG. 2(b) is an illustration of a second intermediate table representing the table after swapping the "w" bit and the "x" bit of the first intermediate table and re-processing of the table to match the modified index. The table index illustrated in FIG. 2(b) is (z,w,y,x) and the table entries are {A,E,C,G,I,M,K,O,B,F,D,H,J,N,L,P} for addresses 0-15 respectively. However the index for the second intermediate table still does not match the index for the new table, therefore, a third swapping operation is performed. FIG. 2(c) is an illustration of a new table representing the table after swapping the "x" bit and the "y" bit of the second intermediate table and re-processing of the table to match the modified index. The table index illustrated in FIG. 2(c) is (z,w,x,y) and the table entries are {A,C,E,G,I,K,M,O,B,D,F,H,J,L,N,P}. The bit-swapping technique frequently requires each table entry to be copied (modified) multiple times, e.g., three time in the above example. This process is time consuming and is not efficient.
Another conventional technique uses an indirect mapping system to accommodate variations in address bit sequences. In this technique an index map is generated and stored in memory that maps each new index value to an old index value. FIG. 3 is an illustration of an index map generated and stored in memory according to a conventional technique. In FIG. 3 a new index (NI) corresponding to (z,w,x,y) is stored in memory and is associated with the corresponding old index (OI) (w,x,y,z). For example, a new index of (1000) corresponds to the old index of (0001) since in both indices the "z" bit is equal to a binary one. The entire index map is generated and stored in memory. In order to access a table entry a new index is identified. Then the new index is mapped to an old index. Then the table entry associated with the old index is retrieved from memory. One problem with the indirect index mapping technique is that the new table index values must be stored in memory. It is not uncommon for the size of the index to exceed sixteen bits. Storing a new index map in the memory can quickly consume a large portion of the scarce memory resources since the number of indices in the index map is 2.sup.N where N is the size of the index in bits. A second problem with the indirect index mapping technique is that, as described above, it is difficult to efficiently receive the new bit sequence information. A third problem with the indirect index mapping technique is that, as described above, in order to identify a table entry, two table lookups are necessary, one map index lookup and one table entry lookup. This indirect mapping is inefficient and time consuming. A fourth problem with the indirect index mapping technique is that conventional systems predefine the index size in order to generate the index maps. For example, in the above example, the computer-based technique used to generate the index map will only operate with four bit index values. It is possible to have techniques for reordering table entries when the number of entries (and hence the number of indicies) will always have a specific length. However, a better solution reorders the table entries when the table size is only determined at run-time, i.e., after the old table and the computer program have been generated. Accordingly, the above technique for generating and storing an index map is not an effective solution in many design environments.
What is needed is a system and method for (1) efficiently identifying a new index bit sequence; (2) utilizing a single technique to rearrange any size table; (3) generating new index it sequences without utilizing a significant amount of memory resources; and (4) rearranging table entries only once.